package LeetCode75;

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 1926. 迷宫中离入口最近的出口
 * 提示
 * 中等
 * 61
 * 相关企业
 * 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
 *
 * 每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
 *
 * 请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
 * 输出：1
 * 解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
 * 一开始，你在入口格子 (1,2) 处。
 * - 你可以往左移动 2 步到达 (1,0) 。
 * - 你可以往上移动 1 步到达 (0,2) 。
 * 从入口处没法到达 (2,3) 。
 * 所以，最近的出口是 (0,2) ，距离为 1 步。
 * 示例 2：
 *
 *
 * 输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
 * 输出：2
 * 解释：迷宫中只有 1 个出口，在 (1,2) 处。
 * (1,0) 不算出口，因为它是入口格子。
 * 初始时，你在入口与格子 (1,0) 处。
 * - 你可以往右移动 2 步到达 (1,2) 处。
 * 所以，最近的出口为 (1,2) ，距离为 2 步。
 * 示例 3：
 *
 *
 * 输入：maze = [[".","+"]], entrance = [0,0]
 * 输出：-1
 * 解释：这个迷宫中没有出口。
 *
 *
 * 提示：
 *
 * maze.length == m
 * maze[i].length == n
 * 1 <= m, n <= 100
 * maze[i][j] 要么是 '.' ，要么是 '+' 。
 * entrance.length == 2
 * 0 <= entrancerow < m
 * 0 <= entrancecol < n
 * entrance 一定是空格子。
 */
public class T1926_离迷宫入口最近的出口 {

    //使用BFS 广度优先搜索 每次步数加一 将下一轮遍历的格子放入队列中
    public int nearestExit(char[][] maze, int[] entrance) {

        return bfs(maze, entrance);

    }

    /**
     * @param maze         迷宫
     * @param currentIndex 当前位置的坐标
     * @return
     */
    private int bfs(char[][] maze, int[] currentIndex) {

//        Queue<int[]> nextStep = new LinkedBlockingQueue<>();
        Queue<int[]> currentStep = new LinkedList<>();

        currentStep.add(currentIndex);
        int step = 0;
        while (!currentStep.isEmpty()) {
            Queue<int[]> nextStep = new LinkedBlockingQueue<>();
            int size = currentStep.size();
            //遍历本轮 所有的空格 为了防止走回头路 将走过的格子设置为别的值 或者变为墙
            for (int i = 0; i < size; i++) {
                int[] spaceIndex = currentStep.poll();
                //检查自身是否是出口 是要是在边界的空格即为出口
                if (spaceIndex[0] == 0 || spaceIndex[1] == 0 || spaceIndex[0] == maze.length - 1 || spaceIndex[1] == maze[0].length - 1) {
                    if (step != 0) {
                        return step;
                    }
                }

                maze[spaceIndex[0]][spaceIndex[1]] = '+';
                //遍历上下左右四个位置 是否是空格 并将附近的空格加入下一轮的队列
                //上
                addQueue(new int[]{spaceIndex[0] - 1, spaceIndex[1]}, nextStep, maze);
                //下
                addQueue(new int[]{spaceIndex[0] + 1, spaceIndex[1]}, nextStep, maze);
                //左
                addQueue(new int[]{spaceIndex[0], spaceIndex[1] - 1}, nextStep, maze);
                //右
                addQueue(new int[]{spaceIndex[0], spaceIndex[1] + 1}, nextStep, maze);
            }
            currentStep = nextStep;
            step++;
        }
        return -1;
    }

    //判断该坐标是否合理 是否是空格 并将空格的坐标加入队列中
    private void addQueue(int[] index, Queue<int[]> queue, char[][] maze) {
        int x = index[0];
        int y = index[1];

        if (x < 0 || x >= maze.length) {
            return;
        }
        if (y < 0 || y >= maze[0].length) {
            return;
        }
        if (maze[x][y] == '.') {
            //入队就要标记 防止重复入队
            maze[x][y] = '+';
            queue.add(index);
        }

    }

    public static void main(String[] args) {
        T1926_离迷宫入口最近的出口 test = new T1926_离迷宫入口最近的出口();
        test.nearestExit(new char[][]{{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}}, new int[]{1, 0});
    }

}
